package com.yan.programercode.chapter_1.question_6;

import java.util.Stack;

/**
 * 汉诺塔问题比较经典，这里修改 一下游戏规则：现在限制不能从最左侧的塔移动到最右侧，也不能从最右侧移动到最左侧，必须经过中间。
 * 求当塔有n层的时候，打印最优移动过程和最优移动总步数
 * 
 * @author Yan
 *
 */
public class HanoiTower {

	public static void main(String[] args) {
		// 递归的方式处理汉诺塔问题
//		System.out.println(hanoiSolve1(3, "left", "mid", "right"));
		
		// 栈的方式处理汉诺塔问题
		System.out.println(hanoiSolve2(3, "left", "mid", "right"));
		
	}

	/**
	 * 使用递归的方式解决汉诺塔问题
	 * 
	 * @param num
	 * @param left
	 * @param mid
	 * @param right
	 * @return
	 */
	public static int hanoiSolve1(int num, String left, String mid, String right){
		if(num < 1){
			return 0;
		}
		return process(num, left, mid, right, left, right);
	}
	
	public static int process(int num, String left, String mid, String right, String from, String to){
		if(num == 1){
			if(from.equals(mid) || to.equals(mid)){
				System.out.println("Move 1 from " + from + " to " + to);
				return 1;
			}else{
				System.out.println("Move 1 from " + from + " to " + mid);
				System.out.println("Move 1 from " + mid + " to " + to);
				return 2;
			}
		}
		
		if(from.equals(mid) || to.equals(mid)){
			String another = (from.equals(left) || to.equals(left)) ? right : left;
			int part1 = process(num-1, left, mid, right, from, another);
			int part2 = 1;
			System.out.println("Move " + num + " from " + from + " to " + to);
			int part3 = process(num-1, left, mid, right, another, to);
			return part1 + part2 + part3;
		}else{
			int part1 = process(num-1, left, mid, right, from, to);
			int part2 = 1;
			System.out.println("Move " + num + " from " + from + " to " + mid);
			int part3 = process(num-1, left, mid, right, to, from);
			int part4 = 1;
			System.out.println("Move " + num + " from " + mid + " to " + to);
			int part5 = process(num-1, left, mid, right, from, to);
			return part1 + part2 + part3 + part4 + part5;
		}
	}
	
	public static int hanoiSolve2(int num, String left, String mid, String right){
		Stack<Integer> ls = new Stack<Integer>();
		Stack<Integer> ms = new Stack<Integer>();
		Stack<Integer> rs = new Stack<Integer>();
		ls.push(Integer.MAX_VALUE);
		ms.push(Integer.MAX_VALUE);
		rs.push(Integer.MAX_VALUE);
		
		for(int i=num;i>0;i--){
			ls.push(i);
		}
		
		Action[] record = {Action.No};
		int step = 0;
		while(rs.size() != num + 1){
			step += fStackTotStack(record, Action.MToL, Action.LToM, ls, ms, left, mid);
			step += fStackTotStack(record, Action.LToM, Action.MToL, ms, ls, mid, left);
			step += fStackTotStack(record, Action.RToM, Action.MToR, rs, ms, right, mid);
			step += fStackTotStack(record, Action.MToR, Action.RToM, ms, rs, mid, right);
		}
		return step;
	}
	
	public static int fStackTotStack(Action[] record, Action preNoAct, Action nowAct, 
			Stack<Integer> fStack, Stack<Integer> tStack, String from, String to){
		if(record[0] != preNoAct && fStack.peek() < tStack.peek()){
			tStack.push(fStack.pop());
			System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
			record[0] = nowAct;
			return 1;
		}
		return 0;
	}
	
}

enum Action{
	No, LToM, MToL, RToM, MToR
}